﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0047)http://clover520.blogbus.com/logs/46796393.html -->
<HTML xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META 
content="一直被传为神话的DancingLink确实很神秘..&#13;&#10;只是把双向链表的删除操作反方向作，它就变成神奇的DancingLink了。&#13;&#10;节点的删除与添加这个舞蹈确实很神奇。&#13;&#10;&nbsp;&#13;&#10;其中Knuth在他自己写的论文中提到了DLX算法，就是用DancingLink优化过的X算法。&#13;&#10;这个算法用来解决一类精确匹配问题。&#13;&#10;一个01矩阵，选出若干行使得所选行可以精..." 
name=description><LINK title="RSS 2.0" 
href="http://clover520.blogbus.com/index.rdf" type=application/rss+xml 
rel=alternate><LINK href="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/50146.css" 
type=text/css rel=stylesheet>
<SCRIPT>if (top.location != self.location) {top.location=self.location;}</SCRIPT>

<SCRIPT type=text/javascript> 
var content_img_width = 550;
</SCRIPT>

<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/resize.js" 
type=text/javascript></SCRIPT>

<META content="MSHTML 6.00.2900.5897" name=GENERATOR></HEAD>
<BODY>
<DIV id=wrapper>
<DIV id=detail>
<DIV id=container>
<DIV id=header>
<DIV class=header-top></DIV>
<H1 class=blogName><A title=http://clover520.blogbus.com 
href="http://clover520.blogbus.com/">天矢の翼</A></H1>
<DIV class=description>[NKU]Angel</DIV>
<DIV class=clear></DIV></DIV>
<DIV id=innerContainer>
<DIV class=innerTop></DIV>
<DIV id=outerContent>
<DIV id=content>
<DIV class=contentTop></DIV>
<UL id=posts>
  <DIV class=postsTop></DIV>
  <DIV class=context><SPAN class=pre><A 
  href="http://clover520.blogbus.com/logs/46368591.html">&lt;&lt;&nbsp;&nbsp;RP高涨</A></SPAN> 
  | <SPAN class=top><A href="http://clover520.blogbus.com/">首 页</A></SPAN> | 
  <SPAN class=next><A 
  href="http://clover520.blogbus.com/logs/46796649.html">poj3740 精确匹配 
  DLX矩阵传递&nbsp;&nbsp;&gt;&gt;</A></SPAN></DIV><!--list-->
  <LI>
  <DIV class=postHeader>
  <H3>2009-09-19</H3>
  <H2>Dancing Link 之DLX算法笔记<SPAN class=category> - [<A 
  href="http://clover520.blogbus.com/c1841152/">武林秘籍</A>]</SPAN></H2></DIV>
  <DIV class=clear></DIV>
  <DIV class=postBody>
  <P class=cc-lisence style="LINE-HEIGHT: 180%"><A 
  href="http://creativecommons.org/licenses/by/3.0/deed.zh" 
  target=_blank>版权声明</A>：转载时请以超链接形式标明文章原始出处和作者信息及<A 
  href="http://bangzhuzhongxin.blogbus.com/logs/11205960.html" 
  target=_blank>本声明</A><BR><A 
  href="http://clover520.blogbus.com/logs/46796393.html">http://clover520.blogbus.com/logs/46796393.html</A><BR><BR></P>
  <P>一直被传为神话的DancingLink确实很神秘..</P>
  <P>只是把双向链表的删除操作反方向作，它就变成神奇的DancingLink了。</P>
  <P>节点的删除与添加这个舞蹈确实很神奇。</P>
  <P>&nbsp;</P>
  <P>其中Knuth在他自己写的论文中提到了DLX算法，就是用DancingLink优化过的X算法。</P>
  <P>这个算法用来解决一类精确匹配问题。</P>
  <P>一个01矩阵，选出若干行使得所选行可以精确覆盖所有列。即在列方向上所有的1不互相重合且没有空列。简单来说，就是选出的这些行中，每列有且只有一个1。</P>
  <P>所谓的X算法，就是：</P>
  <P>每次挑选一个列上1数最少的列去覆盖，然后枚举去覆盖这个列的行。<BR>接下来删掉可以用这个行可以覆盖掉的列，以及可以覆盖掉这个列的行。然后循环。<BR>直到，没有列可以选则匹配成功。否则，若有剩余列中没有1，便返回失败。</P>
  <P><BR>由于一般的精确匹配的应用，矩阵都比较稀疏，所以用十字链表的方法最好。<BR>对于一开始选的要覆盖的列，其实选什么对于结果都是没有影响的，为了让分支更少，扩展的节点更少，就在一开始的时候尽量少扩展。<BR>列的删除和覆盖是两个完全相反的过程，否则就会出现问题。</P>
  <P>这个过程详细的直接去看原版论文，非常详细。</P>
  <P>下面说下对于数独之类的怎么转化为精确匹配模型</P>
  <P>模型的建立自然是要把冲突的条件都摆出来，这里有4个。<BR>1.同行不能有相同的数<BR>2.同列不能有相同的数<BR>3.同块不能有相同的数<BR>除了这3个很显然的约束，还有一个比较重要的，就是<BR>4.每个位置只能有一个数</P>
  <P>所以，对于一个9*9的数独，如此设置行:<BR>(行标号，列标号)，(行标号，数)，(列标号，数)，(块标号，数)<BR>每块都是9*9=81,一共是324个位置。<BR>其中比据我要加入一个i行j列的数字k那么要加入一个含4个1的行，即<BR>(i,j),(i,k),(j,k)(block(i,j),k)<BR>block(i,j)返回(i,j)的块标号<BR>如果有初始值的话把所有初始值都放一起，放在第0行，然后在第1层循环中做下特判，只进行一次覆盖。。如果能保证第一次必然循环到此行就这么做。否则，在递归开始前就先把这些列删除。提出前一种方案只是因为写起来方便。</P>
  <P>如果用矩阵的话，<A href="http://acm.pku.edu.cn/" 
  target=_blank>POJ</A>3470可以当一个练习题。<BR>poj3435数据MS很水。。<BR>poj3120这个可以用搜的办法加几个旋转对称剪枝<BR>poj2676和3074都是经典9*9数独，区别在于SPJ<BR>poj3076是个好的练习题，16*16的格子.</P>
  <P>顺便说一下，由于舞蹈的常数很大，这个对于搜索的优化，在小数据的时候优化程度是非常有限的。</P>
  <P>&nbsp;</P>
  <P>&nbsp;</P>
  <P>&nbsp;</P>
  <DIV class=relpost><BR>
  <H3>随机文章：</H3>
  <DIV><A href="http://clover520.blogbus.com/logs/46796737.html">poj3435 数独 
  DLX二元组传递</A> 2009-09-20</DIV>
  <DIV><A href="http://clover520.blogbus.com/logs/46796649.html">poj3740 精确匹配 
  DLX矩阵传递</A> 2009-09-20</DIV>
  <DIV><A href="http://clover520.blogbus.com/logs/28039502.html">[笔记]状态压缩TSP</A> 
  2008-08-23</DIV>
  <DIV><A href="http://clover520.blogbus.com/logs/26385810.html">[笔记]KM算法</A> 
  2008-07-31</DIV>
  <DIV><A href="http://clover520.blogbus.com/logs/25340442.html">[AC原创]二分查找</A> 
  2008-07-23</DIV></DIV>
  <DIV class=addfav><BR>收藏到：<SPAN class=delicious><A 
  href="http://delicious.com/save?url=http%3A%2F%2Fclover520.blogbus.comhttp%3A%2F%2Fclover520.blogbus.com%2Flogs%2F46796393.html&amp;title=Dancing+Link+%E4%B9%8BDLX%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0" 
  target=_blank>Del.icio.us</A></SPAN></DIV><BR><BR><BR>
  <TABLE style="MARGIN: 0px auto" cellSpacing=0 cellPadding=0 width="99%" 
  align=center border=0>
    <TBODY>
    <TR>
      <TD align=middle>
        <SCRIPT src="" type=text/javascript></SCRIPT>
      </TD></TR></TBODY></TABLE><BR>
  <DIV class=clear></DIV></DIV>
  <DIV class=tags>Tag：<A 
  href="http://clover520.blogbus.com/tag/DancingLink/">DancingLink</A> </DIV>
  <DIV class=postFooter>
  <DIV class=tb_url>引用地址：<INPUT id=trackback_url 
  onmouseover="document.getElementById('trackback_url').select()" 
  value=http://www.blogbus.com/public/tb.php/4344005/46796393/7aa53975109e9887775922ebc1cf7215></DIV>
  <DIV class=menubar><SPAN class=author><A 
  href="http://home.blogbus.com/profile/AngelClover">AngelClover</A></SPAN> 
  发表于<SPAN class=time>23时58分56秒</SPAN> | <A class=edit 
  href="http://www.blogbus.com/user/?mm=Post&amp;aa=Edit&amp;blogid=4344005&amp;id=46796393">编辑</A> 
  | <A class=discuss 
  href="http://www.blogbus.com/user/?mm=Blog&amp;aa=Cite&amp;sblogid=4344005&amp;id=46796393&amp;sid=0&amp;type=1">继续话题</A> 
  | <A class=fwd 
  href="http://www.blogbus.com/user/?mm=Blog&amp;aa=Cite&amp;sblogid=4344005&amp;id=46796393&amp;sid=0&amp;type=0">转发</A> 
  | <A class=dig 
  onclick="share_click('share_dab6370cd8f35527bfa48909c7e5e181');" 
  href="http://app.home.blogbus.com/share?t=DancingLink%E4%B9%8BDLX%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0&amp;url=http%3A%2F%2Fclover520.blogbus.com%2Flogs%2F46796393.html&amp;un=AngelClover&amp;k=12440a7b36bd6df0b86868c2acc2aecc" 
  target=_blank>分享<SPAN 
  id=share_dab6370cd8f35527bfa48909c7e5e181>　0</SPAN></A></DIV></DIV><!--/list-->
  <DIV class=postsBottom></DIV></LI></UL>
<UL id=trackbacks>
  <H2>引用</H2><A name=tb></A>
  <DIV class=desc>下面Blog引用了该文：</DIV>
  <LI>
  <H3><A href="http://clover520.blogbus.com/logs/46796737.html" 
  target=_blank>poj3435 数独 DLX二元组传递</A></H3>
  <DIV class=blogName>Blog：<SPAN>天矢の翼</SPAN></DIV>
  <DIV class=time>2009-09-20 01:01:36</DIV>
  <LI>
  <H3><A href="http://clover520.blogbus.com/logs/46796649.html" 
  target=_blank>poj3740 精确匹配 DLX矩阵传递</A></H3>
  <DIV class=blogName>Blog：<SPAN>天矢の翼</SPAN></DIV>
  <DIV class=time>2009-09-20 00:57:53</DIV></LI></UL>
<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/jquery.js"></SCRIPT>
<LINK href="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/picobox.css" type=text/css 
rel=stylesheet><LINK 
href="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/picobox_beauty.css" 
type=text/css rel=stylesheet>
<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/picobox.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/picobox_beauty.js" 
type=text/javascript></SCRIPT>

<DIV id=commentForm></DIV>
<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/cmt_form.htm" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>var post_ids='46796393';</SCRIPT>

<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/number.htm" 
type=text/javascript></SCRIPT>

<SCRIPT>function share_click(id){var num = parseInt(document.getElementById(id).innerHTML);	num++;document.getElementById(id).innerHTML= ' '+num;}</SCRIPT>

<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/helper1.js" 
type=text/javascript></SCRIPT>

<DIV class=contentBottom></DIV></DIV></DIV>
<DIV id=outerSidebar>
<DIV id=sidebar>
<DIV class=sideTop></DIV>
<DIV class=module id=nPosts>
<DIV class=modTop></DIV>
<H2>最新日志</H2>
<DIV class=modBody>
<UL>
  <LI><A 
  href="http://clover520.blogbus.com/logs/50051421.html">WHU之行很不好意思的总结</A> 
  <LI><A href="http://clover520.blogbus.com/logs/47292910.html">转一个常用定理表</A> 
  <LI><A href="http://clover520.blogbus.com/logs/46796737.html">poj3435 数独 
  DLX二元组传递</A> 
  <LI><A href="http://clover520.blogbus.com/logs/46796649.html">poj3740 精确匹配 
  DLX矩阵传递</A> 
  <LI><A href="http://clover520.blogbus.com/logs/46796393.html">Dancing Link 
  之DLX算法笔记</A> 
  <LI><A href="http://clover520.blogbus.com/logs/46368591.html">RP高涨</A> 
  <LI><A href="http://clover520.blogbus.com/logs/46281402.html">ft...郁闷的网络赛</A> 
  <LI><A href="http://clover520.blogbus.com/logs/45909667.html">Rp过首轮..</A> 
  <LI><A href="http://clover520.blogbus.com/logs/45448363.html">Orz了现在这状态</A> 
  <LI><A 
  href="http://clover520.blogbus.com/logs/43635270.html">[zz]批处理for命令详解(2)</A> 
  </LI></UL>
<DIV class=more><A 
href="http://clover520.blogbus.com/logs/">全部日志&gt;&gt;</A></DIV></DIV>
<DIV class=modBottom></DIV></DIV>
<DIV class=module id=nComments>
<DIV class=modTop></DIV>
<H2>最新评论</H2>
<DIV class=modBody>
<UL>
  <LI><SPAN class=author>落儿</SPAN>：<A 
  href="http://clover520.blogbus.com/logs/50051421.html#cmt">其实不错了。。。毕竟是新组的队。。。...</A>
  <LI><SPAN class=author>LonelyBoy</SPAN>：<A 
  href="http://clover520.blogbus.com/logs/47292910.html#cmt">Orz...</A>
  <LI><SPAN class=author>sdfond</SPAN>：<A 
  href="http://clover520.blogbus.com/logs/46368591.html#cmt">弱弱的问一下，那个哈尔滨网络赛的D题，有什么论文有相关的...</A>
  <LI><SPAN class=author><A href="http://clover520.blogbus.com/" 
  target=_blank>AngelClover</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/46796737.html#cmt">接楼主.. bool dfs(int 
  leve...</A>
  <LI><SPAN class=author><A href="http://clover520.blogbus.com/" 
  target=_blank>AngelClover</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/46796649.html#cmt">ft....居然超长...继续.. 
  voi...</A>
  <LI><SPAN class=author><A href="http://www.cppblog.com/abilitytao" 
  target=_blank>abilitytao</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/42615558.html#cmt">to alpc43 
  貌似这个题你的代码有点问题吧~~~...</A>
  <LI><SPAN class=author><A href="http://nudt/" 
  target=_blank>alpc43</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/42615558.html#cmt"> 我在PKU 的mail 
  &gt;??? 我怎么没有收到...</A>
  <LI><SPAN class=author><A href="http://nudt/" 
  target=_blank>alpc43</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/42615558.html#cmt">我不是大牛~~~~我也是最近才在学这个东西~~~你的QQ...</A>
  <LI><SPAN class=author><A href="http://taiwan/" 
  target=_blank>康皓華</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/45909667.html#cmt">您好，我是路过的网友，平时也有在写ACM，不知道能否跟您...</A>
  <LI><SPAN class=author><A href="http://nudt/" 
  target=_blank>alpc43</A></SPAN>：<A 
  href="http://clover520.blogbus.com/logs/42615558.html#cmt"> 
  貌似这个题你的代码有点问题吧~~~给你两组数据 a...</A></LI></UL></DIV>
<DIV class=modBottom></DIV></DIV>
<DIV class=module id=meta>
<DIV class=modTop></DIV>
<DIV class=modBody>
<UL>
  <LI class=subscribe style="LINE-HEIGHT: 180%">
  <DIV><A href="http://clover520.blogbus.com/index.rdf"><IMG alt=RSS 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/rss.gif"></A> <A 
  href="http://bangzhuzhongxin.blogbus.com/logs/5452786.html" 
  target=_blank>什么是RSS？</A></DIV>
  <DIV class=inezha style="MARGIN: 0.5em 0px"><A title=此博客内容更新用IM提醒我 
  href="http://inezha.com/add2?hid=2320&amp;url=http://clover520.blogbus.com/index.rdf" 
  target=_blank><IMG alt=用IM提醒我内容更新 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/anothr.gif"></A></DIV>
  <DIV class=qqmail style="MARGIN: 0.5em 0px"><A title=订阅到QQ邮箱 
  href="http://mail.qq.com/cgi-bin/feed?u=http://clover520.blogbus.com/index.rdf" 
  target=_blank><IMG alt=订阅到QQ邮箱 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/qqmail.png"></A></DIV>
  <DIV class=xiangguo style="MARGIN: 0.5em 0px"><A title=订阅到鲜果阅读器 
  href="http://www.xianguo.com/subscribe.php?url=http://clover520.blogbus.com/index.rdf" 
  target=_blank><IMG alt=订阅到鲜果阅读器 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/xianguo.png"></A></DIV>
  <DIV class=g-reader style="MARGIN: 0.5em 0px"><A title=订阅到Google阅读器 
  href="http://fusion.google.com/add?feedurl=http://clover520.blogbus.com/index.rdf" 
  target=_blank><IMG alt=订阅到Google阅读器 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/google.png"></A></DIV>
  <DIV class=zhuaxia style="MARGIN: 0.5em 0px"><A title=订阅到抓虾阅读器 
  href="http://www.zhuaxia.com/add_channel.php?url=http://clover520.blogbus.com/index.rdf" 
  target=_blank><IMG alt=订阅到抓虾阅读器 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/zhuaxia.png"></A></DIV>
  <LI class=poweredBy><A class=iCityLogo 
  style="BACKGROUND: none transparent scroll repeat 0% 0%" 
  href="http://www.icity.cn/catalog" target=_blank><IMG 
  style="MARGIN-BOTTOM: 5px" alt=《城客》第四期：创意之城 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/icity_cover_200908.jpg"></A><BR><A 
  href="http://www.blogbus.com/" target=_blank><IMG alt=博客大巴 
  src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/link_blogbus.gif"></A>
  <DIV><A title=博客大巴使用指南 href="http://bangzhuzhongxin.blogbus.com/" 
  target=_blank>博客大巴使用指南</A></DIV>
  <DIV><A title=博客大巴模板中心 href="http://www.blogbus.com/skin/" 
  target=_blank>博客大巴模板中心</A></DIV>
  <DIV><A title=免费注册博客大巴 href="http://www.blogbus.com/user/reg.php" 
  target=_blank>免费注册博客大巴</A></DIV>
  <DIV><A title=一键博客搬家工具 href="http://banjia.blogbus.com/" 
  target=_blank>一键博客搬家工具</A></DIV>
  <DIV><A title=中文互动杂志城客 href="http://www.icity.cn/" 
  target=_blank>中文互动杂志城客</A></DIV></LI></UL></DIV>
<DIV class=modBottom></DIV></DIV>
<DIV class=sideBottom></DIV></DIV></DIV>
<DIV class=innerBottom></DIV></DIV>
<DIV class=clear></DIV>
<DIV id=footer>
<DIV class=copyright>Copyright © 2002-2009 BlogBus.com, All Rights Reserved. <A 
href="http://www.blogbus.com/" target=_blank>博客大巴</A> 版权所有 <BR><A 
href="http://new-skin146.blogbus.com/">博客大巴模板设计： 绿芽 | 作者： 小明</A> 
</DIV></DIV></DIV></DIV></DIV>
<SCRIPT 
src="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files\helper1(1).js" 
type=text/javascript></SCRIPT>

<SCRIPT type=text/javascript>
        var gaJsHost = (("https:" == document.location.protocol)?"https://ssl." : "http://www.");
        document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
        </SCRIPT>

<SCRIPT type=text/javascript>
        var pageTracker = _gat._getTracker("UA-2120146-1");
        pageTracker._setDomainName(".blogbus.com");
        pageTracker._addOrganic("baidu","word");
        pageTracker._addOrganic("baidu","wd");
        pageTracker._addOrganic("soso","w");
        pageTracker._addOrganic("vnet","kw");
        pageTracker._initData();
        pageTracker._trackPageview();
        </SCRIPT>

<SCRIPT src="Dancing Link 之DLX算法笔记 - 天矢の翼 - 博客大巴.files/counter.js.htm" 
type=text/javascript></SCRIPT>
</BODY></HTML>
